/*
Search in Rotated Sorted Array II Total Accepted: 41823 Total Submissions: 134067 My Submissions Question Solution
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.
*/
#include <iostream>
#include "print.h"
#include <vector>
#include <map>
#include <algorithm>

using namespace std;


/***/
//Definition for an interval.
struct Interval {
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};
class Solution {
public:
	bool search(vector<int>& nums, int target) {
		int left = 0;
		int right = nums.size() - 1;

		while (left <= right)
		{
			int mid = left + (right - left) / 2;
			
			if (nums[mid] == target)
			{
				return true;
			}
			bool isLeft = true;
			for (int i = left; i <= mid; i++)
			{
				if (nums[i]>nums[mid])
				{
					isLeft = false;
					break;
				}

			}

			if (isLeft)
			{
				if (nums[left]<= target && target < nums[mid])
				{
					right = mid - 1;
				}
				else
				{
					left = mid + 1;
				}
			}
			else 
			{
				if (nums[mid]< target && target <= nums[right])
				{
					left = mid + 1;
				}
				else
				{
					right = mid - 1;
				}
			}
			

		}
		return false;
	}
};

class Solution1 {
public:
	bool search(vector<int>& nums, int target) {
		int left = 0;
		int right = nums.size()-1;

		while (left < right)
		{
			int mid = left + (right - left) / 2;
			if (nums[left] < target && target <nums[mid])
			{
				right = mid - 1;
			}
			else if (nums[mid] < target && target <nums[right])
			{
				left = mid + 1;
			}
			else
			{
				if (nums[left] != target) left++;
				else return true;
				
				if (nums[right]!=target)
				{
					right--;
				}
				else
				{
					return true;
				}


				
			}

		}
		return false;
	}
};



struct Foo
{
	Foo(){ }
	Foo(int){ }
	void fun() { }

};

void test()
{
	int a = 1, b = 2, c = 3, d = 4;
	int e = (a < b ? a : c < d ? a : d);
	cout << e << endl;
}

int main()
{
	int a[] = { 5,1,3};
	vector<int> nums(a, a + sizeof(a) / sizeof(int));
	Solution s;

	bool flag = s.search(nums,3);


	system("pause");
	return 0;
}